package Z.dailyExercise._0223;

public class _剑指Offer55II平衡二叉树 {
    /**
     * 递归 相当于从底向上
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if (helper(root) == -1){
            return false;
        }else {
            return true;
        }
    }

    //计算结点高度 只有满足平衡的情况下
    public int helper(TreeNode node){
        if (node == null){
            return 0;
        }

        int lefth = helper(node.left);
        int righth = helper(node.right);
        if (lefth == -1 || righth==-1){
            return -1;
        }

        if (Math.abs(lefth-righth)>1){
            return -1;
        }

        return Math.max(lefth,righth)+1;

    }

    /**
     * 从上到下方法
     */
    public boolean isBalanced1(TreeNode root) {

        if (root == null){
            return true;
        }

        return Math.abs(heplerH(root.right,1)-heplerH(root.left,1))<2
                && isBalanced1(root.left) && isBalanced1(root.right);

    }

    //帮助计算当前高度 从上倒下
    public int heplerH(TreeNode node ,int curh){
        if (node == null){
            return curh;
        }

        curh++;
        return Math.max(heplerH(node.left,curh),heplerH(node.right,curh));
    }
}
